package binarytree

import "math"

func isValidBST(root *TreeNode) bool {
	upper := math.MaxInt64
	lower := math.MinInt64
	return isValidBST_helper(root, lower, upper)
}

func isValidBST_helper(root *TreeNode, lower int, upper int) bool {
	if root == nil {
		return true
	}

	if root.Val <= lower || root.Val >= upper {
		return false
	}

	return isValidBST_helper(root.Left, lower, root.Val) && isValidBST_helper(root.Right, root.Val, upper)
}

func isValidBST_LDR(root *TreeNode) bool {

	sorted := []int{}
	isValidBST_LDR_helper(root, sorted)

	for i := 1; i < len(sorted); i++ {
		if sorted[i] < sorted[i-1] {
			return false
		}
	}
	return true

}

// 中序遍历
func isValidBST_LDR_helper(root *TreeNode, sorted []int) []int {

	if root.Left != nil {
		sorted = append(sorted, isValidBST_LDR_helper(root.Left, sorted)...)
	}

	sorted = append(sorted, root.Val)

	if root.Right != nil {
		sorted = append(sorted, isValidBST_LDR_helper(root.Right, sorted)...)
	}

	return sorted
}
